package org.zofia.zipfs;


import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class ZipfsMain {
	
	private static int songsNumber = 0;  
	private static int songsToSelect= 0 ;
	private static String regex1 = "[a-z_0-9]{1,30}";
	private static long tenpowertvelve = 1000000000000L;
	private static long mainPlayed = 0L;
	private static int[] resultSmall;
	private static String[] resultTitle;
	private static int[] resultLineNo;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
	   
		Scanner stdin = new Scanner(new BufferedInputStream(System.in));
		//Scanner stdin = new Scanner(System.in);
		try {
			String zeroLine = stdin.nextLine();
			String[] words = zeroLine.split(" "); 
			if (words == null || words.length!=2){
				//System.out.print("First line incorrect format, not two numbers");
				System.exit(0);
			}
			songsNumber = Integer.parseInt(words[0]);
			songsToSelect = Integer.parseInt(words[1]);
		} catch (InputMismatchException ex1){
			//System.out.print("Wrong format of the input data");
			System.exit(0);
		} catch (NoSuchElementException ex2){
			//System.out.print("Wrong format of the input data -There is no integer");
			System.exit(0);
		} catch (IllegalStateException ex3){
			//System.out.print("Problem reading the input (scanner closed)");
			System.exit(0);
		} catch (NumberFormatException ex){
			//System.out.print("First line incorrect format");
			System.exit(0);
		}
		
		if ((songsNumber <= 0) || (songsToSelect <= 0)
				|| (songsToSelect > songsNumber) || (songsNumber > 50000)){
			//System.out.print("No songs or too many songs to process");
			System.exit(0); 
		}
		
		String line = "";
		int lineNo = 1;
		boolean errorInLine = false;
		resultSmall = new int[songsToSelect];
		resultTitle = new String[songsToSelect];
		resultLineNo = new int[songsToSelect];
		try {
			while (stdin.hasNextLine()) {
				line = stdin.nextLine();
				if (isCorrectFormatAddToResult(line, lineNo)) {
					lineNo++;
				} else {
					errorInLine = true;
					break;
				}
				
			}

		} catch (RuntimeException tyGNojuTy) {
			errorInLine = true;
			//System.out.print("Error while reading lines");
		} finally {
			if (stdin != null) {
				stdin.close();
			}
			
		}

		if (errorInLine) {
			//System.out.print("Line " + lineNo + " has incorrect format");
			System.exit(0);
		} else if ((lineNo - 1) != songsNumber) {
			//System.out.print("Expected " + songsNumber + " of songs but got "
				//	+ (lineNo - 1));
			System.exit(0);
		}
		int counter = songsToSelect-1 ;			
			while (counter>=0){		
				try {
					System.out.write(resultTitle[counter].getBytes());
					//System.out.println(resultSmall[counter]+" "+resultTitle[counter]);
					if (counter != 0){
						System.out.write('\n');
					}
					counter--;
				} catch (IOException e) {
				//System.out.print("Failed to write to the out stream");
				System.exit(0);
				}
				
			}
		
}

	
	private static void addToResult(long count, String title, int lineNo) {
		
		int indexToPutNewNumber = 0;
		boolean bigger = false;
		double factor = getMainPlayed()/lineNo;
		int quality =  (int) (((count)/factor)*10000000.00);
		//System.out.println("Adding to result lineNo "+lineNo+ " with quality "+quality);
		for (int i = 0; i<songsToSelect; i++){
			if (resultSmall[i]>= quality){
				if (resultSmall[i]==quality && resultLineNo[i] > lineNo){
					indexToPutNewNumber=i;	
				} else {
					indexToPutNewNumber=i-1;
					
				}
				bigger=true;
				break;	
			}
		}
		
		if (!bigger){
			indexToPutNewNumber=songsToSelect-1;
		}
		
		
		for (int j=0; j<indexToPutNewNumber; j++){
				resultSmall[j]=resultSmall[j+1];
				resultTitle[j]=resultTitle[j+1];
				resultLineNo[j]=resultLineNo[j+1];
				
		}
		
		
		if (indexToPutNewNumber >=0){
			resultSmall[indexToPutNewNumber]=quality;
			resultTitle[indexToPutNewNumber]=title;
			resultLineNo[indexToPutNewNumber]=lineNo;
		}
		
	}

	

	private static boolean isCorrectFormatAddToResult(String line, int lineNo) {
		if (line == null){
			return false;
		}
		if (line.charAt(0)==' ') {
			return false;
		}
		if (line.charAt(line.length()-1)==' '){
			return false;
		}
		String[] words = line.split(" ");
		if (words== null || words.length != 2) {
			return false;
		}

		try {
			long count = Long.parseLong(words[0], 10);
			if ( count < 0L) { //listen count < 
				return false;
			} else if (count > tenpowertvelve ){
				return false;
			}
			
			if (words[1].matches(regex1)) { //if matches the regex; 
				if (lineNo == 1){
					setMainPlayed(count);
				}
				addToResult(count, words[1], lineNo);
				return true;
			} else {
				return false;
			}
		} catch (NumberFormatException ex){
			return false;
		}
		

		

		
	}

	protected static long getMainPlayed() {
		return mainPlayed;
	}
	
	protected static void setMainPlayed(long mainPlayed) {
		ZipfsMain.mainPlayed = mainPlayed;
	}
}

	